#!/usr/bin/ruby
# Segundo Trabalho Prático de Teoria dos Grafos e Algoritmos
# Anderson Tiago, Caio Almeida e Flávio Escobar
# Semestre 2009.1

# Classes definitions
require 'classes'

# Create a graph
g = Graph.new

# Create vertices
gets.to_i.times { g.add_vertex Vertex.new(gets.chomp) }

# Create edges
g.get_vertices.each do |v|
	line = gets.split.collect{ |k| k.to_i }
	line.each_index { |i|	v.connect_to g.get_vertex(i) if line[i] == 1 }
end

# Is it a chordal graph?
if g.is_chordal?
	chromatic_number = 0
	g.cliques.each do |c|
		puts c.collect{ |v| v.get_label }.join('-')
		chromatic_number = c.size if c.size > chromatic_number
	end
	puts chromatic_number
else
	puts 'O grafo nao e triangulado.'
end
puts
